﻿using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Mindless
{
    static class Algorithm
    {
        /// <summary>
        /// Sorts the given range of the given list using the given comparison.
        /// </summary>
        /// <remarks>
        /// Follows Sedgewick: 1) Use median-of-three partitioning, 2) Do not attempt to quicksort
        /// small ranges. However, this is a double recursive implementation - we assume a large
        /// stack. Implementation also based on:
        /// http://www.java2s.com/Code/Java/Collections-Data-Structure/Quicksortwithmedianofthreepartitioning.htm
        /// </remarks>
        public static void Sort<T>(IList<T> list, int iLeft, int iRight, Comparison<T> comparison)
        {
                // start with quicksort to get the list *mostly* sorted
            QuickSort(list, iLeft, iRight, comparison);

                // finish with insertion sort (which works better if the input is nearly sorted)
            InsertionSort(list, iLeft, iRight, comparison);

            Debug.Assert(IsSorted(list, iLeft, iRight, comparison));
        }

        /// <summary>
        /// Quick-sorts the given range of the given list using the given comparison. Note that this
        /// implementation does not completely sort the list.
        /// </summary>
        static void QuickSort<T>(IList<T> list, int iLeft, int iRight, Comparison<T> comparison)
        {
            const int THRESHOLD = 10;
            if (iRight - iLeft > THRESHOLD)
            {
                T pivot = MedianOf3(list, iLeft, iRight, comparison);
                int iPivot = Partition(list, iLeft, iRight, comparison, pivot);
                QuickSort(list, iLeft, iPivot - 1, comparison);
                QuickSort(list, iPivot + 1, iRight, comparison);
            }
        }

        /// <summary>
        /// Basic insertion sort.
        /// </summary>
        static void InsertionSort<T>(IList<T> list, int iLeft, int iRight, Comparison<T> comparison)
        {
            for (int i = iLeft + 1; i <= iRight; ++i)
            {
                T t = list[i];
                int j = i - 1;
                while ((j >= iLeft) && (comparison(list[j], t) == 1))
                {
                    list[j + 1] = list[j];
                    j -= 1;
                }
                list[j + 1] = t;
            }
        }

        /// <summary>
        /// Indicates whether the given range of the given list is sorted.
        /// </summary>
        static bool IsSorted<T>(IList<T> list, int iLeft, int iRight, Comparison<T> comparison)
        {
            bool isSorted = true;
            for (int i = iLeft + 1; i <= iRight; ++i)
            {
                if (comparison(list[i-1], list[i]) == 1)
                {
                    isSorted = false;
                    break;
                }
            }

            return isSorted;
        }

        /// <summary>
        /// Picks three members of the given list (within the given range) and sorts them
        /// in-place. Then moves the middle one to the end of the list and returns its value.
        /// </summary>
        static T MedianOf3<T>(IList<T> list, int iLeft, int iRight, Comparison<T> comparison)
        {
                // need at least three items in range
            Debug.Assert(iRight - iLeft + 1 >= 3);

            int iMid = (iRight + iLeft) / 2;
            if (comparison(list[iLeft], list[iMid]) == 1)
                Swap(list, iLeft, iMid);
            if (comparison(list[iLeft], list[iRight]) == 1)
                Swap(list, iLeft, iRight);
            if (comparison(list[iMid], list[iRight]) == 1)
                Swap(list, iMid, iRight);

                // move the pivot to the penultimate slot
            Swap(list, iMid, iRight - 1);

            return list[iRight - 1];
        }

        /// <summary>
        /// Partitions the given list (within the given range) so that everything to the right of the
        /// given pivot is >= the pivot and everything to the left of the pivot is <= the pivot. Then
        /// answers the new location of the pivot value.
        /// </summary>
        static int Partition<T>(IList<T> list, int iLeft, int iRight, Comparison<T> comparison, T pivot)
        {
                // assume MedianOf3 was run
            Debug.Assert(iRight - iLeft + 1 >= 3);

            int iLeftScan = iLeft;         // points to the first of the presorted three
            int iRightScan = iRight - 1;   // points to the pivot, which is the middle of the presorted three

                // scan for out of place items
            while (true)
            {
                    // scan forward until we find an item >= pivot
                while (comparison(list[++iLeftScan], pivot) == -1)
                    ;

                    // scan backward until we find an item <= pivot
                while (comparison(list[--iRightScan], pivot) == 1)
                    ;

                    // pointers crossed? - if so, scan done
                if (iLeftScan >= iRightScan)
                    break;
                else
                    Swap(list, iLeftScan, iRightScan);
            }
                // put the pivot in its correct location
            Swap(list, iLeftScan, iRight - 1);

            return iLeftScan;
        }

        /// <summary>
        /// Swaps the given items of the given list.
        /// </summary>
        static void Swap<T>(IList<T> list, int iA, int iB)
        {
            T temp = list[iA];
            list[iA] = list[iB];
            list[iB] = temp;
        }

        static void Main()
        {
            int[] array = { 3, 1, 4, 1, 5, 9, 2, 6 };
            Algorithm.Sort(array, 0, array.Length - 1, delegate(int x, int y) { return x.CompareTo(y); });
        }
    }
}
